Information Theory, Inference and Learning Algorithms Lecture 2

课程主页：http://www.inference.org.uk/mackay/itprnn/，http://www.inference.org.uk/itprnn_lectures/

课程视频：https://www.bilibili.com/video/BV14b411G7wn?from=search&seid=1786094286746981315，https://www.youtube.com/watch?v=BCiZc0n6COY&list=PLruBu5BI5n4aFpG32iMbdWoRVAA-Vcso6

课程书籍：https://book.douban.com/subject/1893050/

这次回顾第二讲，第二讲介绍了熵的概念。

备注：笔记参考了中文书籍。

熵和相关函数的定义

结果为$x$的香农信息量定义为

$$h(x)=\log _{2} \frac{1}{P(x)}$$

总体$X$的熵定义为香农信息量的期望

$$H(X) \equiv \sum_{x \in \mathscr{G}_{X}} P(x) \log \frac{1}{P(x)}$$

方便起见，也将$H(X)$记作$H(p)$，其中

$$p=\left(p_{1}, p_{2}, \cdots, p_{I}\right)$$

那么

$$H(p) =\sum_{i} p_i \log \frac{1}{p_i}$$

$X$和$Y$的联合熵为

$$H(X, Y)=\sum_{x y \in \mathscr{G}_{X} \mathscr{G}_{Y}} P(x, y) \log \frac{1}{P(x, y)}$$

性质

1. $H(X)\ge 0$，当且仅当存在$x$，使得$P(x)=1$时等号成立。
2. $H(X) \le \log \left(\left|\mathscr{B}_{X}\right|\right)$，当且仅当$P(x)=\frac 1 {|\mathscr G_X|}$时等号成立。

1.证明：

$$P(x) \log \frac{1}{P(x)} \ge 0$$

当且仅当$P(x)=1$时等号成立。

所以

$$H(X) \equiv \sum_{x \in \mathscr{G}_{X}} P(x) \log \frac{1}{P(x)} \ge 0$$

注意到

$$0\log \frac 1 0 =0$$

所以当且仅当存在$x$，使得$P(x)=1$时等号成立。

2.证明：

利用凸函数的性质可得

$$H(X) \equiv \sum_{x \in \mathscr{G}_{X}} P(x) \log \frac{1}{P(x)} \le \log \sum_{x \in \mathscr{G}_{X}} P(x) \frac{1}{P(x)} = \log \left(\left|\mathscr{B}_{X}\right|\right)$$

当且仅当$P(x)=\frac 1 {|\mathscr H_X|}$时等号成立。

熵的可分解性

$$\begin{aligned} H(\boldsymbol{p})=& H\left[\left(p_{1}+p_{2}+\cdots+p_{m}\right),\left(p_{m+1}+p_{m+2}+\cdots+p_{I}\right)\right] \\ &+\left(p_{1}+\cdots+p_{m}\right) H\left(\frac{p_{1}}{\left(p_{1}+\cdots+p_{m}\right)}, \cdots, \frac{p_{m}}{\left(p_{1}+\cdots+p_{m}\right)}\right) \\ &+\left(p_{m+1}+\cdots+p_{t}\right) H\left(\frac{p_{m+1}}{\left(p_{m+1}+\cdots+p_{I}\right)}, \cdots, \frac{p_{I}}{\left(p_{m+1}+\cdots+p_{I}\right)}\right) \end{aligned}$$

特别的，对于$m=1$，我们有

$$H(p)=H\left(p_{1}, 1-p_{1}\right)+\left(1-p_{1}\right) H\left(\frac{p_{2}}{1-p_{1}}, \frac{p_{3}}{1-p_{1}}, \cdots, \frac{p_{I}}{1-p_{I}}\right)$$

证明：

$$\begin{aligned} H\left[\left(p_{1}+p_{2}+\cdots+p_{m}\right),\left(p_{m+1}+p_{m+2}+\cdots+p_{I}\right)\right] &= \left(\sum_{i=1}^m p_i\right) \log \frac 1 { \sum_{i=1}^m p_i}+\left(\sum_{i=m+1}^I p_i\right) \log \frac 1 { \sum_{i=m+1}^I p_i} \\ \left(p_{1}+\cdots+p_{m}\right) H\left(\frac{p_{1}}{\left(p_{1}+\cdots+p_{m}\right)}, \cdots, \frac{p_{m}}{\left(p_{1}+\cdots+p_{m}\right)}\right) &= \left(\sum_{i=1}^m p_i\right) \left(\sum_{j=1}^m \frac {p_j} {\sum_{i=1}^m p_i} \log \frac {\sum_{i=1}^m p_i}{p_j}\right)\\ &=\sum_{j=1}^m {p_j}\log \frac {\sum_{i=1}^m p_i}{p_j} \\ &=\sum_{j=1}^m {p_j}\log \frac 1{p_j}+ \log \left(\sum_{i=1}^m p_i\right) \sum_{j=1}^m {p_j} \\ \left(p_{m+1}+\cdots+p_{t}\right) H\left(\frac{p_{m+1}}{\left(p_{m+1}+\cdots+p_{I}\right)}, \cdots, \frac{p_{I}}{\left(p_{m+1}+\cdots+p_{I}\right)}\right) &= \left(\sum_{i=m+1}^I p_i\right) \left(\sum_{j=m+1}^I \frac {p_j} {\sum_{i=m+1}^I p_i} \log \frac {\sum_{i=m+1}^I p_i}{p_j}\right)\\ &=\sum_{i=m+1}^I {p_j}\log \frac {\sum_{i=m+1}^I p_i}{p_j} \\ &= \sum_{j=m+1}^I {p_j}\log \frac 1{p_j}+ \log \left( \sum_{j=m+1}^I p_i\right) \sum_{j=m+1}^I {p_j} \end{aligned}$$

三者相加即可得到$H(p)$

Gibbs不等式

概率分布$P(x)$和$Q(x)$的相对熵（KL散度）为

$$D_{\mathrm{KL}}(P \| Q)=\sum_{x} P(x) \log \frac{P(x)}{Q(x)}$$

相对熵满足Gibbs不等式

$$D_{\mathrm{KL}}(P \| Q) \geqslant 0$$

当且仅当$P=Q$时取等号。

证明：

令

$$f(u)=\log \frac 1 u$$

利用Jenson不等式，我们有

$$E[f(u)]\ge f(E[u])$$

取$u=\frac {Q(x)}{P(x)}$，概率分布为$P(x)$，那么

$$\begin{aligned} D_{\mathrm{KL}}(P \| Q) &=\sum_{x} P(x) \log \frac{P(x)}{Q(x)}\\ &=E\left[f\left(\frac {Q(x)}{P(x)}\right) \right] \\ &\ge f\left(E\left[\frac {Q(x)}{P(x)}\right]\right)\\ &= f(1)\\ &=0 \end{aligned}$$

凸函数以及Jenson不等式

函数$f$在$(a,b)$上是凸的，如果对所有$x_{1}, x_{2} \in(a, b)$和$0\le \lambda \le 1$，都有

$$f\left(\lambda x_{1}+(1-\lambda) x_{2}\right) \leqslant \lambda f\left(x_{1}\right)+(1-\lambda) f\left(x_{2}\right)$$

凸函数的图示如下：

Jenson不等式

如果$f$是凸函数，$x$是随机变量，那么

$$\mathbb E[f(x)]\ge f(\mathbb E[x])$$